home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / scbench.arc / SORT.C < prev    next >
Text File  |  1980-01-01  |  5KB  |  256 lines
  1.  
  2. /*
  3. ** BYTE Sort Benchmark
  4. ** Version 1 for 8088/8086/80286/80386
  5. ** Feb. 17, 1988
  6. ** Written in BYTE Small-C
  7. ** Based on Small-C by J.E. Hendrix
  8. **
  9. ** Sorts integer array of random numbers using 3 methods:
  10. ** QUICKSORT
  11. ** SHELLSORT
  12. ** HEAPSORT
  13. **
  14. ** The QUICKSORT and HEAPSORT algorithms used were adapted from
  15. ** examples given by G.H. Gonnet in his excellent HANDBOOK OF
  16. ** ALGORITHMS AND DATA STRUCTURES -- Addison Wesley
  17. ** ISBN 0-201-14218-X.
  18. ** The SHELLSORT algorithms was adapted from a version presented
  19. ** in Neill Graham's MICROPROCESSOR PROGRAMMING FOR COMPUTER
  20. ** HOBBYISTS, Tab Books, ISBN 0-8306-6952-3.
  21. **
  22. ** The benchmark operates as follows:
  23. ** 1. Build an array of random integers.
  24. ** 2. Turn on the stopwatch.
  25. ** 3. Perform QUICKSORT
  26. ** 4. Turn off the stopwatch.
  27. ** 5. Accumulate total time.
  28. ** 6. Re-build array of random integers.
  29. ** 7. Turn on the stopwatch.
  30. ** 8. Perform SHELLSORT.
  31. ** 9. Turn off the stopwatch.
  32. ** 10. Add elapsed time to total.
  33. ** 11. Re-build array of random integers.
  34. ** 12. Turn on the stopwatch.
  35. ** 13. Perform HEAPSORT.
  36. ** 14. Turn off the stopwatch.
  37. ** 15. Add elapsed time to total.
  38. ** 16. Print out results.
  39. **
  40. */
  41.  
  42. #include stdio.h        /* Standard I/O */
  43. #define ASIZE 8000        /* Array size */
  44.  
  45. int tblock[4];            /* Timer block */
  46. int tacc[4];            /* Timer accumulator */
  47. int seed;            /* Random number seed */
  48.  
  49. main()
  50. {
  51.     int sarray[ASIZE];    /* Array to sort */
  52.  
  53.     /* Announce yourself */
  54.     printf("BYTE Sort Benchmark\n\n");
  55.  
  56.     /* Build random array */
  57.     seed=0;
  58.     getrand(sarray);
  59.  
  60.     printf("--QUICKSORT\n");
  61.     /* Turn on timer */
  62.     gtime(tblock);
  63.  
  64.     /* QUICKSORT */
  65.     qsort(sarray,0,ASIZE-1);
  66.  
  67.     /* Turn off timer and accumulate time */
  68.     calctim(tblock);
  69.     acctime();
  70.  
  71.     /* Build another random array */
  72.     seed=0;
  73.     getrand(sarray);
  74.  
  75.     printf("--SHELLSORT\n");
  76.     /* Turn on timer */
  77.     gtime(tblock);
  78.  
  79.     /* SHELLSORT */
  80.     shsort(sarray,0,ASIZE-1);
  81.  
  82.     /* Turn off timer and accumulate time */
  83.     calctim(tblock);
  84.     acctime();
  85.  
  86.     /* Build another random array */
  87.     seed=0;
  88.     getrand(sarray);
  89.  
  90.     /* Turn on timer */
  91.     gtime(tblock);
  92.  
  93.     printf("--HEAPSORT\n");
  94.     /* HEAPSORT */
  95.     hsort(sarray,0,ASIZE-1);
  96.  
  97.     /* Turn off timer and accumulate time */
  98.     calctim(tblock);
  99.     acctime();
  100.  
  101.     /* Report */
  102.  
  103.     printf("Total sorting time: (HH:MM:SS:1/100)\n");
  104.     printf("%d:%d:%d:%d\n\n",tacc[0],tacc[1],tacc[2],tacc[3]);
  105.  
  106.     printf("Press RETURN for operating system:");
  107.     fgetc(stdin);
  108.     exit(0);
  109.  
  110. }
  111.  
  112. /* QUICKSORT 
  113. ** qsort(array,bot,top)
  114. ** int array[] - array to sort
  115. ** bot - Index to first element in array[]
  116. ** top - Index to last element in array[]
  117. */
  118. qsort(aray,bot,top) int aray[],bot,top;
  119. {
  120.     int i,j,temp;
  121.  
  122.   while(bot<top) {
  123.  
  124.     /* Set ranges and choose partitioning element */
  125.     i=bot;
  126.     j=top;
  127.     temp=aray[bot];
  128.  
  129.     /* Partition array */
  130.     while(i<j) {
  131.       while(aray[j]>temp) j-=1;
  132.       aray[i]=aray[j];
  133.       while((i<j)&&(aray[i]<=temp)) i+=1;
  134.       aray[j]=aray[i];
  135.     }
  136.     aray[i]=temp;
  137.  
  138.     /* Call qsort recursively */
  139.     qsort(aray,bot,i-1);
  140.     bot=i+1;
  141.   }
  142. }
  143.  
  144. /*
  145. ** SHELLSHORT
  146. ** shsort(array,bot,top)
  147. ** int array[] - array to sort
  148. ** bot - Index to first element in array[]
  149. ** top - Index to last element in array[]
  150. */
  151. shsort(aray,bot,top) int aray[],bot,top;
  152. {
  153.     int i,gap,nex,temp;
  154.  
  155.     
  156.     gap=(top-bot)/2;    /* Set gap width */
  157.     do {
  158.       do {
  159.         nex=1;        /* No exchanges yet */
  160.         for(i=0;i<=top-gap;++i )
  161.         {  if(aray[i]>aray[i+gap])
  162.            {  temp=aray[i];
  163.               aray[i]=aray[i+gap];
  164.               aray[i+gap]=temp;
  165.               nex=0;    /* An exchange happened */
  166.            }
  167.         }
  168.       } while(nex==0);
  169.       gap=gap/2;
  170.     } while(gap!=0);
  171.  
  172. }
  173.  
  174. /*
  175. ** HEAPSORT
  176. ** hsort(aray,bot,top)
  177. ** int array[] - array to sort
  178. ** bot - Index to first element in array[]
  179. ** top - Index to last element in array[]
  180. */
  181. hsort(aray,bot,top) int aray[],bot,top;
  182. {
  183.     int i,temp;
  184.  
  185.     /* First...make a heap */
  186.     for(i=(top/2);i>1;--i)
  187.         sift(aray,i,top);
  188.     /* Extract maximum */
  189.     for(i=top;i>1;--i) {
  190.       sift(aray,0,i);
  191.       temp=aray[0];
  192.       aray[0]=aray[i];
  193.       aray[i]=temp;
  194.     }
  195. }
  196.  
  197. sift(aray,i,j) int aray[],i,j;
  198. {
  199.     int k,temp;
  200.  
  201.     while((2*i)<=j) {
  202.       k=2*i;
  203.       if(k<j)
  204.         if(aray[k]<aray[k+1]) ++k;
  205.  
  206.       if(aray[i]<aray[k]) {
  207.         temp=aray[k];
  208.         aray[k]=aray[i];
  209.         aray[i]=temp;
  210.         i=k;
  211.       }
  212.       else i=j+1;
  213.     }
  214.     return;
  215. }
  216.  
  217. /*
  218. ** Getrand()
  219. ** Builds an array of random numbers.
  220. */
  221. getrand(array) int array[];
  222. {
  223.     int i;
  224.  
  225.     for(i=0;i<ASIZE;++i) {
  226.         seed=rand(seed);
  227.         array[i]=seed;
  228.     }
  229. }
  230.  
  231. /*
  232. ** acctime()
  233. ** Accumulate time stored in tblock[] into tacc[]
  234. */
  235. acctime()
  236. {
  237.     tacc[3]+=tblock[3];    /* Hundredths */
  238.     if(tacc[3]>=100) {
  239.         tacc[2]+=1;
  240.         tacc[3]-=100;
  241.     }
  242.     tacc[2]+=tblock[2]; /* Seconds */
  243.     if(tacc[2]>=60) {
  244.         tacc[1]+=1;
  245.         tacc[2]-=60;
  246.     }
  247.     tacc[1]+=tblock[1]; /* Minutes */
  248.     if(tacc[1]>=60) {
  249.         tacc[0]+=1;
  250.         tacc[1]-=60;
  251.     }
  252.     tacc[0]+=tblock[0];    /* Hours */
  253.     return;
  254. }
  255.  
  256.